Integrated circuits, such as system-on-chips (SoCs), typically implement one or more complex finite state machines (FSMs) which transition between states in response to input events and/or based on a computation on the internal state of the FSM.
The interplay between input events and computations based on the internal state of the FSM often results in dependencies, hazards and race conditions resulting in the FSM being in a livelock or a deadlock. A FSM is in deadlock if it has reached a state where no combination of inputs, or combination of internal state interactions, will cause the state to be exited (i.e. it is not possible to transition out of the state). In contrast, a FSM is in livelock if it can transition between states (i.e. it is not stuck in a single state as with deadlock), but it infinitely cycles through the same set of states. For example, a FSM that infinitely cycles through three states A, B and C (e.g. A->B->C->A->B->C . . . ) is said to be in livelock.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods and systems for detecting livelock in an integrated circuit.